package leetcode.code0427;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

//执行用时：1 ms, 在所有 Java 提交中击败了21.15%的用户
//
//内存消耗：41.4 MB, 在所有 Java 提交中击败了6.73%的用户
//
//通过测试用例：22 / 22
public class Solution implements IDebug {

	public Node construct(int[][] grid) {
		int n = grid.length;
		return this.divide(grid, 0, n - 1, 0, n - 1);
	}

	private Node divide(int[][] grid, int rl, int rr, int cl, int cr) {
		if (rl == rr && cl == cr) {
			return new Node(grid[rl][cl] == 1, true);
		}
		int rm = ((rr - rl) >> 1) + rl;
		int cm = ((cr - cl) >> 1) + cl;
		Node topLeft = this.divide(grid, rl, rm, cl, cm);
		Node topRight = this.divide(grid, rl, rm, cm + 1, cr);
		Node bottomLeft = this.divide(grid, rm + 1, rr, cl, cm);
		Node bottomRight = this.divide(grid, rm + 1, rr, cm + 1, cr);
		if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf && topLeft.val == topRight.val
				&& topRight.val == bottomLeft.val && bottomLeft.val == bottomRight.val) {
			return new Node(topLeft.val, true);
		}
		return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
	}

	@Override
	public void debug1() {

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.construct(HelpDebug.str2array1("[[0,1],[1,0]]"));
	}

	class Node {
		public boolean val;
		public boolean isLeaf;
		public Node topLeft;
		public Node topRight;
		public Node bottomLeft;
		public Node bottomRight;

		public Node() {
			this.val = false;
			this.isLeaf = false;
			this.topLeft = null;
			this.topRight = null;
			this.bottomLeft = null;
			this.bottomRight = null;
		}

		public Node(boolean val, boolean isLeaf) {
			this.val = val;
			this.isLeaf = isLeaf;
			this.topLeft = null;
			this.topRight = null;
			this.bottomLeft = null;
			this.bottomRight = null;
		}

		public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
			this.val = val;
			this.isLeaf = isLeaf;
			this.topLeft = topLeft;
			this.topRight = topRight;
			this.bottomLeft = bottomLeft;
			this.bottomRight = bottomRight;
		}
	}

}
